1. Field of the Invention
This invention relates generally to cryptographic communication systems and, more particularly, to public-key cryptographic systems in which the use of two keys, a public and private key, facilitates both secret and authentic transmission of data. A public-key cryptosystem can be used for identification, electronic signatures, key-distribution, and secure data communication. Specific applications of a public-key cryptosystem include automated bank tellers exchanging data with customer chip-cards, point of service banking, telecommunications, electronic mail, and access control.
2. Description of the Prior Art
The two primary cryptographic functions required by modern communications systems are secrecy and authenticity. Secret transmission of data over an insecure channel is a well established cryptographic function. This data may be a message-to-be-transferred or a key-to-be-exchanged. Another cryptographic function is the authentication of electronic messages (or verification of identity by electronic means). Authentication is particularly a concern with electronic communications because of the potential for tampering and forging digital messages.
Cryptosystems can be classified into two types: private-key and public-key. Private-key cryptosystems (also referred to as single-key or symmetrical cryptosystems), such as the DES scheme (data encryption standard), use the same key for encryption and decryption. These ciphers can be fast and hard to break but a threat to their security is the distribution of the private key.
Public-key cryptography was introduced by W. Diffie and M. E. Hellman in "New directions in cryptography", IEEE Trans. Inform. Theory, vol. IT-22, 1976, pp. 644-654. Public-key, two-key, or asymmetrical cryptosystems address the problem of distributing a secret key over an insecure channel by using two keys. Each party has their own secret decoding key and a mathematically related public encoding key, which can be publicly distributed without compromising the secrecy of the associated decoding key. Secret communication employs the pair of keys belonging to the receiver and an electronic signature makes use of the pair of keys of the sender.
A message M can be enciphered by sender A, with a publicly available encoding key E.sub.B generated by party B, that can only be deciphered by receiver B with the matching private key D.sub.B. For secret transmission from party A to party B, the ciphertext C is enciphered by party A as C=E.sub.B (M) and deciphered by party B as D.sub.B (C)=D.sub.B (E.sub.B (M))=M. For authenticity, the sender A applies the decoding function to the message with his/her own private key D.sub.A and the receiver B unscrambles the message by applying the encoding function with the sender's public key E.sub.A. To verify that a message M from party A is authentic, a signature C=D.sub.A (M) is generated by party A and the signature is verified by party B as E.sub.A (C)=E.sub.A (D.sub.A (M))=M.
There are variations on the above basic Diffie and Hellman protocol such as concatenating standard data with the message, which is checked by the receiver, or signing a hashed (compressed) form of the message. To check identity, the verifier challenges the candidate to sign a random number (which is checked with the public key of the candidate) or to decrypt an enciphered random number. There are some public-key schemes that can only be used for signatures or secret transmission of data (but not both), while other schemes can provide both secrecy and authenticity. The public-key of each user can be placed in a public file, which can be distributed through a trusted key-distribution center to detect tampering.
Diffie and Hellman proposed a key distribution scheme (not a two-key cryptosystem) depending on the discrete logarithm problem (see U.S. Pat. No. 4,200,770). The first implementation of the public key concept was the Rivest, Shamir, and Adleman (RSA) algorithm (see U.S. Pat. No. 4,405,829), which depends on the discrete logarithm and factoring problems. Other public-key-cryptosystems based on the discrete logarithm and factoring problems include the public-key cryptosystem of T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory, vol. 31, 1985, pp. 469-472, and the signature schemes of M. O. Rabin, "Digital signatures and public-key functions as intractable as factorization", internal report of the MIT Laboratory for Computer Science, MIT/LCS/TR-212, 1979; T. Okamoto, "A fast signature scheme based on congruential polynomial operations", IEEE Transactions on Information Theory, vol. IT-36, pp. 47-53, 1990; A. Fiat and A. Shamir (European patent application Ser. No. 0,252,499 and U.S. Pat. No. 4,748,668); L. C. Gillou and J. -J. Quisquater, "A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory", Advances in Cryptology EUROCRYPT '88, Berlin: Springer-Verlag, 1988, pp. 123-128; and Schnorr (U.S. Pat. No. 4,995,082 and European patent application Ser. No. 0,384,475).
The problem to be solved with many of the above schemes is the amount of computation for encoding and/or decoding. They all include modular exponentiation in the encoding and decoding function, which has a large time complexity O(k.sup.3) where k is the number of bits in the exponent and modulus. Interactive schemes, such as those of Schnorr, Gillou-Quisquater, and Fiat-Shamir have considerably less computation than RSA but tradeoff probability of cheating and storage space for accreditation terms. Precomputation is possible with Okamoto's and Schnorr's schemes, which is an advantage in applications such as chip cards.
An identification scheme based on the permuted-kernels problem and a zero-knowledge protocol was proposed by A. Shamir (see U.S. Pat. No. 4,932,056), which has a small amount of computation but has large signatures (relative to the Fiat-Shamir scheme) and requires about 10 Kbits of interactive communication between the verifier and the candidate.
A public-key cryptosystem based on error correcting codes was proposed by R. J. McEliece described in "A public key cryptosystem based on algebraic coding theory", JPL DSN Progress Report 42-44, January-February 1978, pp. 114-116, which has several orders of magnitude less computation than RSA but has a message expansion factor of two (in bits) and a relatively large public-key of 2.sup.19 bits. Riek and McFarland described several techniques for implementing McEliece's cryptosystem (see U.S. Pat. No. 5,054,066). However, McEliece's cryptosystem was broken by V. I. Korzhik and A. I. Turkin as described in "Cryptanalysis of McEliece's public-key cryptosystem", Advances in Cryptology EUROCRYPT '91, Berlin: Springer-Verlag, 1991, pp. 68-70.
In 1978, R. C. Merkle and M. E. Hellman proposed a public-key cryptosystem based on the knapsack problem in "Hiding information and signatures in trapdoor knapsacks" IEEE Trans. Inform. Theory, vol. IT-24, 1978, pp. 525-530 (also see U.S. Pat. No. 4,218,582), that encrypts and decrypts about a hundred times faster than RSA. The knapsack weights are initially selected as a superincreasing series and then disguised by modular multiplication. Henry described a method of decoding the single-iterated Merkle-Hellman knapsack cryptosystem called "double-encryption" (see U.S. Pat. No. 4,399,323). However, Shamir broke the single-iterated Merkle-Hellman cryptosystem in 1984. Eventually all of the fast knapsack-type cryptosystems (Merkle and Hellman's scheme and variants proposed subsequently) were broken. The cryptanalysis of knapsack cryptosystems is reviewed by E. F. Brickell and A. M. Odlyzko in "Cryptanalysis: A survey of recent results", Proceedings of the IEEE, vol. 76, May 1988, pp. 578-592.
A fast knapsack-type public-key cryptosystem was proposed by S. C. Lu and L. N. Lee in "A simple and effective public-key cryptosystem", COM. SAT. Tech, Rev., vol. 9, no. 1, 1979, pp. 15-24, where the Chinese remainder theorem and a residue number system are used to select the initial knapsack weights. Several variants of the Lu-Lee cryptosystem were also proposed: B. S. Adiga and P. Shankar, "Modified Lu-Lee cryptosystem", Electronic Letters, vol. 21, no. 18, August 1985, pp. 794-795 and R. M. Goodman and A. J. McAuley, "New trapdoor knapsack public key cryptosystem", IEE Proceedings, vol. 132, part E, no. 6, November 1985, pp. 289-292. However, the Lu-Lee cryptosystem and all of its variants were broken as reviewed by Brickell and Odlyzko.
The main weakness in the broken knapsack schemes is their reliance on modular multiplication as the disguising technique. Brickell and Odlyzko stated in their 1988 paper that "These unusually good simultaneous diophantine approximations can be used to break all of the knapsack cryptosystems that have been proposed that rely on modular multiplications as a disguising technique" and "The Chor and Rivest knapsack cryptosystem is the only Knapsack cryptosystem that has been published that does not use some form of modular multiplication to disguise an easy knapsack". Chor and Rivest's knapsack cryptosystem, described in "A knapsack type public-key cryptosystem based on arithmetic in finite fields", Advances in Cryptology CRYPTO '84, Berlin: Springer-Verlag, 1985, pp. 54-65, is still unbroken but employs modular exponentiation for decryption and, as a result, has similar speed to RSA.
Compact knapsacks, such as the Lu-Lee cryptosystem, employ fewer knapsack weights and have larger coefficients representing the message, which results in a smaller public-key. However, if the number of knapsack weights is smaller than about four, then linear integer programming techniques can be used to decode the ciphertext without finding the private key (see Brickell and Odlyzko's review paper). Knapsack cryptosystems with many weights (three or more) are vulnerable to simultaneous diophantine approximation while those with few weights (four or less) are subject to integer programming.
Several knapsack-type cryptosystems have been proposed in the last few years. H. Isselhorst proposed a generalized knapsack cryptosystem, where a matrix is disguised by multiplying each element by the same fractional constant, in "The use of fractions in public-key cryptosystems", Advances in Cryptology EUROCRYPT '89, Berlin: Springer-Verlag, 1990, pp. 47-55. However, Isselhorst's scheme was broken by J. Stern and P. Toffin as described in "Cryptanalysis of a public-key cryptosystem based on approximations by rational numbers", Advances in Cryptology EUROCRYPT '90, Berlin: Springer-Verlag, 1991, pp. 47-55. V. Niemi has recently a knapsack cryptosystem related to algebraic coding theory, involving a matrix multiplication as the disguising operation, in "A new trapdoor in knapsacks", Advances in Cryptology EUROCRYPT '90, Berlin: Springer-Verlag, 1990, pp. 47-55, but his scheme has a relatively large public-key of 20 kbits and can not perform signatures. Niemi's cryptosystem was recently broken by Y. M. Chee, A. Joux, and J. Stern as described in "The cryptanalysis of a new public-key cryptosystem based on modular knapsacks", in Advances in Cryptology CRYPTO '91, Berlin: Springer-Verlag, 1991, pp. 204-212. C. S. Laih, J. Y. Lee, L. Harn, and Y. K. Su. recently proposed modifying the Merkle-Hellman scheme by adding a random term to each knapsack weight in "Linearly shift knapsack public-key cryptosystem", IEEE Journal Selected Areas in Communication, vol. 7, no. 4, May 1989, pp. 534-539, although decryption involves further computation and the public-key is about 40 kbits. L. X. Duan and C. C. Lian proposed a nonlinear form of the Lu-Lee cryptosystem involving modular exponentiation in "Modified LU LEE cryptosystems", Electronic Letters, vol. 25, no. 13, 1989, pp. 826, but their scheme was broken by L. D. Xing and L. G. Sheng in "Cryptanalysis of new modified Lu-Lee cryptosystems" Electronic Letters, vol. 26, no. 19, September 1990, pp. 1601-1602.
To summarize the prior art, the previously proposed public key cryptosystems that remain unbroken have problems to be solved in at least one of the following respects: the amount of computation for encoding and decoding, public and private key size, message expansion, communication delay, and signature size.